10165. Функция f(n)

 

Функция f(n) задана рекуррентным соотношением:

f(n) = f(n – 1) + f(n – 2) + ... + f(2) + f(1),

f(1) = 1

Найдите значение f(n) mod 123456789.

 

Вход. Одно натуральное число n (1 ≤ n ≤ 109).

 

Выход. Выведите значение f(n) mod 123456789.

 

Пример входа 1

Пример выхода 1

3

2

 

 

Пример входа 2

Пример выхода 2

10

256

 

 

РЕШЕНИЕ

рекурсия

 

Анализ алгоритма

Вычислим первые значения функции:

f(1) = 1,

f(2) = f(1) = 1,

f(3) = f(2) + f(1) = 1 + 1 = 2,

f(4) = f(3) + f(2) + f(1) = 2 + 1 + 1 = 4,

f(5) = f(4) + f(3) + f(2) + f(1) = 4 + 2 + 1 + 1 = 8

Можно заметить, что f(n) = 2n–2 при n > 1. Докажем это методом математической индукции.

База индукции. f(2) = 22–2 = 20 = 1.

Шаг индукции. Если предположить что

f(n) = f(n – 1) + f(n – 2) + ... + f(2) + f(1) = 2n–2,

 то

f(n + 1) = f(n) + (f(n – 1) + f(n – 2) + ... + f(2) + f(1)) = 2 * f(n) = 2n–1.

 

Реализация алгоритма

Функция powmod вычисляет значение xn mod m.

 

long long powmod(long long x, long long n, long long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

return (x * powmod(x, n - 1, m)) % m;

}

 

Основная часть программы. Читаем входное значение n.

 

scanf("%lld", &n);

 

Вычисляем и выводим ответ.

 

if (n == 1) res = 1;

else res = powmod(2, n - 2, 123456789);

printf("%lld\n", res);